class Solution {
public:
    vector<int> v;
    int fib(int n) {
        v.resize(n + 1, -1);
        return dfs(n);
    }
    int dfs(int n)
    {
        if (v[n] != -1)
            return v[n];

        if (n == 1 || n == 0)
        {
            v[n] = n;
            return v[n];
        }

        v[n] = dfs(n - 1) + dfs(n - 2);
        return v[n];
    }
};
class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> v(n + 1, vector<int>(n + 1, 0));
        return dfs(1, n, v);
    }
    int dfs(int begin, int end, vector<vector<int>>& v)
    {
        if (begin >= end) return 0;
        if (v[begin][end] != 0) return v[begin][end];
        int ret = INT_MAX;
        for (int i = begin; i <= end; i++)
        {
            int right = dfs(i + 1, end, v);
            int left = dfs(begin, i - 1, v);
            ret = min(ret, i + max(left, right));
        }
        v[begin][end] = ret;
        return ret;
    }
};
class Solution {
public:
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    int flag[201][201];
    int row, col;
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        row = matrix.size();
        col = matrix[0].size();
        int ret = 0;
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                ret = max(ret, dfs(i, j, matrix));
            }
        }
        return ret;
    }
    int dfs(int i, int j, vector<vector<int>>& matrix)
    {
        if (flag[i][j] != 0) return flag[i][j];
        int ret = 1;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < row && y >= 0 && y < col && matrix[x][y] > matrix[i][j])
                ret = max(ret, dfs(x, y, matrix) + 1);
        }
        flag[i][j] = ret;
        return ret;
    }
};
